package 中等.滑动窗口;

/**
 * 给你一个整数数组 nums 和一个 正整数 k 。
 * 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
 * 子数组是数组中的一个连续元素序列。
 *
 * @date 2024/08/04
 * https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/
 */
public class 统计最大元素出现至少K次的子数组_2962 {

    public static void main(String[] args) {

        System.out.println(countSubarrays(new int[]{61, 23, 38, 23, 56, 40, 82, 56, 82, 82, 82, 70, 8, 69, 8, 7, 19, 14, 58, 42, 82, 10, 82, 78, 15, 82}, 2));

    }

    /**
     * 滑动窗口
     * 先找到最大元素，窗口里面有 k 个最大元素
     */
    public static long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int curK = 0;
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] == max) {
                curK++;
            } else {
                if (curK == k-1) {
                    ans += left;
                    right++;
                    continue;
                }
            }
            if (curK < k) {
                right++;
                continue;
            }

            while (left < nums.length && curK >= k) {
                if (nums[left] == max) {
                    curK--;
                }
                left++;
            }

            ans += left;
            right++;
        }

        return ans;
    }

}
